/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
class Solution
{
public:
    class mycomparision
    {
    public:
        bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs)
        {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        //这道题主要是学习一下堆
        //为了保留前k个高频元素，使用小顶堆，删除频率低的元素
        unordered_map<int, int> a; //统计出现频率
        for (int i = 0; i < nums.size(); i++)
        {
            a[nums[i]]++;
        }
        vector<int> res;
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparision> que;
        for (auto it = a.begin(); it != a.end(); it++)
        {
            que.push(pair<int, int>(it->first, it->second));
            if (que.size() > k)
            {
                //如果加入后大于k
                que.pop();
            }
        }
        while (k--)
        {
            res.push_back(que.top().first);
            que.pop();
        }
        return res;
    }
};
// @lc code=end
